{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Single Element in a Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: singleNonDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序数组中的单一元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。</p>\n",
    "\n",
    "<p>请你找出并返回只出现一次的那个数。</p>\n",
    "\n",
    "<p>你设计的解决方案必须满足 <code>O(log n)</code> 时间复杂度和 <code>O(1)</code> 空间复杂度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,1,2,3,3,4,4,8,8]\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums =  [3,3,7,7,10,11,11]\n",
    "<strong>输出:</strong> 10\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i]&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [single-element-in-a-sorted-array](https://leetcode.cn/problems/single-element-in-a-sorted-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [single-element-in-a-sorted-array](https://leetcode.cn/problems/single-element-in-a-sorted-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,3,3,4,4,8,8]', '[3,3,7,7,10,11,11]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        lo, hi = 0, len(nums) - 1\n",
    "        while lo < hi:\n",
    "            mid = 2 * ((lo + hi) // 4)\n",
    "            if nums[mid] == nums[mid+1]:\n",
    "                lo = mid+2\n",
    "            else:\n",
    "                hi = mid\n",
    "        return nums[lo]\n",
    "        \n",
    "        \n",
    "\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        l=0\n",
    "        h=len(nums)-1\n",
    "        while l<h:\n",
    "            mid=int(l+(h-l)/2)\n",
    "            if mid%2==1:\n",
    "                mid-=1\n",
    "            if nums[mid]==nums[mid+1]:\n",
    "                l=mid+2\n",
    "            else:\n",
    "                h=mid\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        \n",
    "        start,end=0,len(nums)-1\n",
    "        mid=(start+end)//2\n",
    "        frontnums,rearnums=deque(nums[:mid]),deque(nums[mid:])\n",
    "        if frontnums[-1]==rearnums[0]:\n",
    "            if len(frontnums)>len(rearnums):\n",
    "                rearnums.appendleft(frontnums.pop())\n",
    "            else:frontnums.append(rearnums.popleft())\n",
    "            \n",
    "        if len(frontnums)%2==1:\n",
    "            newnums=self.singleNonDuplicate(list(frontnums))\n",
    "        if len(rearnums)%2==1:\n",
    "            newnums=self.singleNonDuplicate(list(rearnums))\n",
    "            \n",
    "        return newnums\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return reduce(operator.xor,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        set_nums = set(nums)\n",
    "        \n",
    "        return sum(set_nums)*2 -sum(nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        N=len(nums)\n",
    "        if N==0:\n",
    "            return nums[0]\n",
    "        if nums[0]!=nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[N-2]!=nums[N-1]:\n",
    "            return nums[N-1]\n",
    "        l=0\n",
    "        r=N-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if (mid+1)%2==0 and nums[mid]==nums[mid-1]:\n",
    "                l=mid+1\n",
    "            elif (mid+1)%2==1 and nums[mid]==nums[mid+1]:\n",
    "                l=mid+2\n",
    "            else:\n",
    "                r=mid\n",
    "        return nums[l]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        return sum(nums[::2])*2-sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: list) -> int:\n",
    "        l = []\n",
    "        while nums:\n",
    "            a = nums.pop()\n",
    "            b = True\n",
    "            for i in range(0, len(l)):\n",
    "                if a == l[i]:\n",
    "                    l.pop(i)\n",
    "                    b = False\n",
    "                    break\n",
    "            if b:\n",
    "                l.append(a)\n",
    "        return l[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums) -1\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i <= n:\n",
    "            if len(stack) == 0:\n",
    "                x = nums.pop()\n",
    "                stack.append(x)\n",
    "                i += 1\n",
    "                continue\n",
    "            x = nums.pop()\n",
    "            if x in stack:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "            else:\n",
    "                stack.append(x)\n",
    "                i += 1\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # 方法1、哈希表\n",
    "        # 方法2、数学\n",
    "        # 方法3、二分查找\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if nums[0]!=nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[-1]!=nums[-2]:\n",
    "            return nums[-1]\n",
    "        left,right = 0,len(nums)-1\n",
    "        while left<=right:\n",
    "            middle = (left+right)//2\n",
    "            if nums[middle]==nums[middle+1]:\n",
    "                if middle%2==0:\n",
    "                    left=middle+1\n",
    "                else:\n",
    "                    right=middle-1\n",
    "            elif nums[middle]==nums[middle-1]:\n",
    "                if middle%2==0:\n",
    "                    right = middle-1\n",
    "                else:\n",
    "                    left = middle+1\n",
    "            else:\n",
    "                return nums[middle]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        return sum(set(nums)) * 2 - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        lo = 0\n",
    "        hi = len(nums) - 1\n",
    "        while lo < hi:\n",
    "            mid = (hi- lo)//2 + lo\n",
    "            if nums[mid] == nums[mid+1]:\n",
    "                halves_are_even = (hi - mid -1) % 2 == 1\n",
    "                if halves_are_even:\n",
    "                    lo = mid + 2\n",
    "                else:\n",
    "                    hi = mid - 1\n",
    "            elif nums[mid] == nums[mid-1]:\n",
    "                halves_are_even = (hi - mid) % 2 == 1\n",
    "                if halves_are_even:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid - 2\n",
    "            else:\n",
    "                return nums[mid]\n",
    "        return nums[lo]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # 方法一\n",
    "        numsdic = collections.Counter(nums)\n",
    "        data = sorted(numsdic.items(), key = lambda x: x[1])\n",
    "        return data[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        lo,hi = 0,len(nums)-1\n",
    "        while lo<hi:\n",
    "            mid = lo+(hi-lo)//2\n",
    "            iseven = (hi-mid)%2==0\n",
    "            if nums[mid]==nums[mid+1]:\n",
    "                if iseven:\n",
    "                    lo =mid+2\n",
    "                else:\n",
    "                    hi =mid-1\n",
    "            elif nums[mid-1]==nums[mid]:\n",
    "                if iseven:\n",
    "                    hi=mid-2\n",
    "                else:\n",
    "                    lo=mid+1\n",
    "            else:\n",
    "                return nums[mid]\n",
    "        return nums[lo]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if mid%2==1:\n",
    "                mid-=1\n",
    "            if nums[mid]==nums[mid+1]:\n",
    "                left=mid+2\n",
    "            else:\n",
    "                right=mid\n",
    "        return nums[left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        k = 0\n",
    "        j = len(nums) - 1\n",
    "        while k < j:\n",
    "            m = k + (j-k)//2\n",
    "            b = (j-m)%2 == 0\n",
    "            if nums[m] == nums[m+1]:\n",
    "                if b:\n",
    "                    k = m + 2\n",
    "                else:\n",
    "                    j = m - 1\n",
    "            elif nums[m] == nums[m-1]:\n",
    "                if b:\n",
    "                    j = m - 2\n",
    "                else:\n",
    "                    k = m + 1\n",
    "            else:\n",
    "                return nums[m]\n",
    "        return nums[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "\n",
    "        if nums[l]!=nums[l+1]:\n",
    "            return nums[l]\n",
    "        if nums[r]!=nums[r-1]:\n",
    "            return nums[r]\n",
    "\n",
    "        while l<r:\n",
    "            mid=int(l+(r-l)/2)\n",
    "            check = (mid-l)%2==0 #odd\n",
    "\n",
    "            if nums[mid]!=nums[mid-1] and nums[mid]!=nums[mid+1]:\n",
    "                return nums[mid]\n",
    "            elif nums[mid]!=nums[mid+1]:\n",
    "                if check:\n",
    "                    r=mid-2\n",
    "                else:\n",
    "                    l=mid+1\n",
    "            else:\n",
    "                if check:\n",
    "                    l=mid+2\n",
    "                else:\n",
    "                    r=mid-1\n",
    "\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        nums_count = dict(collections.Counter(nums))\n",
    "        sort_nums_count = sorted(nums_count.items(), key=lambda x:x[1])\n",
    "        return sort_nums_count[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = set(nums[i] for i in range(0,len(nums),2))-set(nums[i] for i in range(1,len(nums),2))\n",
    "        return tuple(res)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#输入: nums =  [3,3,7,7,10,11,11]\n",
    "#输出: 10\n",
    "#哈希表\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        new_list=[]\n",
    "        new_list2=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in new_list:\n",
    "                new_list.append(nums[i])\n",
    "            elif nums[i] in new_list:\n",
    "                new_list2.append(nums[i]) \n",
    "        x=list(set(new_list)^set(new_list2)) \n",
    "        return x[0]   \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        even = [nums[i] for i in range(0,len(nums),2)]\n",
    "        odd = [nums[i] for i in range(1,len(nums)-1,2)]\n",
    "        return (set(even) ^ set(odd)).pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def _method1(self, nums):\r\n",
    "        low, high = 0, len(nums)-1\r\n",
    "\r\n",
    "        while low < high:\r\n",
    "            middle = low+(high-low)//2\r\n",
    "            halvesAreEven = (high-middle)%2 == 0\r\n",
    "            if nums[middle+1] == nums[middle]:\r\n",
    "                if halvesAreEven:\r\n",
    "                    low = middle+2\r\n",
    "                else:\r\n",
    "                    high = middle-1\r\n",
    "            elif nums[middle-1] == nums[middle]:\r\n",
    "                if halvesAreEven:\r\n",
    "                    high = middle-2\r\n",
    "                else:\r\n",
    "                    low = middle+1\r\n",
    "            else:\r\n",
    "                return nums[middle]\r\n",
    "\r\n",
    "        return nums[low]\r\n",
    "\r\n",
    "    def _method2(self, nums: List[int]) -> int:\r\n",
    "        if len(nums) == 1:\r\n",
    "            return nums[0]\r\n",
    "        while len(nums) > 1:\r\n",
    "            i = nums.pop()\r\n",
    "            j = nums.pop()\r\n",
    "            if i != j:\r\n",
    "                return i\r\n",
    "            else:\r\n",
    "                return self._method2(nums)\r\n",
    "\r\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\r\n",
    "        return self._method2(nums)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums):\n",
    "            res=nums.pop(0)\n",
    "            while len(nums)>=2:\n",
    "                tmp=nums.pop()^nums.pop(0)\n",
    "                res=res^tmp\n",
    "            return res\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if nums[-1]-nums[-2]:\n",
    "            return nums[-1]\n",
    "        for i in range(0,len(nums)-1):\n",
    "            nums[i]-=nums[i+1]\n",
    "            if nums[i]!=0 and (nums[i+1]-nums[i+2]==0) and nums[i-1]!=0:\n",
    "                return nums[i]+nums[i+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for x in nums:\n",
    "            res^=x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans ^= num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        return nums[bisect_left(range(len(nums) - 1), True, key=lambda x: nums[x] != nums[x ^ 1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        def run(l, r):\n",
    "            mid = (l + r) // 2\n",
    "            if nums[mid-1] < nums[mid] < nums[mid+1]:\n",
    "                return nums[mid]\n",
    "            \n",
    "            if mid % 2:\n",
    "                if nums[mid] == nums[mid+1]:\n",
    "                    return run(l, mid-1)\n",
    "                else:\n",
    "                    return run(mid + 1, r)\n",
    "            else:\n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    return run(l, mid-1)\n",
    "                else:\n",
    "                    return run(mid + 1, r)\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if nums[0] != nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[-1] != nums[-2]:\n",
    "            return nums[-1]\n",
    "        return run(0, len(nums) - 1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        sidelen = len(nums) // 2\n",
    "        mid = sidelen\n",
    "        while sidelen:\n",
    "            if nums[mid] ^ nums[mid-1] and nums[mid] ^ nums[mid+1]: break\n",
    "            flag = sidelen % 2\n",
    "            sidelen = sidelen // 2\n",
    "            if nums[mid] == nums[mid-1]:\n",
    "                mid = mid + (sidelen + 1) * (1 if flag else -1)\n",
    "            else:\n",
    "                mid = mid - (sidelen + 1) * (1 if flag else -1)\n",
    "            sidelen -= (flag == 0)\n",
    "        return nums[mid]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if nums[mid] == nums[mid^1]:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        def left_or_right(num):\n",
    "            l = len(num)\n",
    "            #if l == 3\n",
    "            i = l // 2\n",
    "            if i % 2 == 0:\n",
    "                if num[i] == num[i-1]:\n",
    "                    return -1\n",
    "                elif num[i] == num[i+1]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                if num[i] == num[i-1]:          #[1,2,2]\n",
    "                    return 1\n",
    "                elif num[i] == num[i+1]:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 0\n",
    "        x = length\n",
    "        new_num = nums\n",
    "        while len(new_num) > 2 :\n",
    "            res = left_or_right(new_num)\n",
    "            L = len(new_num)//2\n",
    "            if res == -1:\n",
    "                if L == 1 :\n",
    "                    return new_num[0]\n",
    "                elif L % 2 == 0:\n",
    "                    new_num = new_num[:L+1]\n",
    "                else:\n",
    "                    new_num = new_num[:L]\n",
    "            elif res == 1:      #[2]\n",
    "                if L==1:\n",
    "                    return new_num[2]\n",
    "                elif L % 2 == 0:\n",
    "                    new_num = new_num[L:]  # [2,2,3,3,4,4,5,6,6,7,7]\n",
    "                else:\n",
    "                    new_num = new_num[L+1:]     \n",
    "            else:\n",
    "                return new_num[L]    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        #如果mid是偶数，比较nums[mid]和nums[mid+1]是否一样\n",
    "        #如果mid是奇数，比较nums[mid]和nums[]mid-1]是否一样\n",
    "        n=0\n",
    "        for i in nums:\n",
    "            n^=i\n",
    "        return (n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # a = nums[0]\n",
    "        # for b in nums[1:]:\n",
    "        #     a = a ^ b\n",
    "\n",
    "        # return(a)\n",
    "\n",
    "        ###### (3) ######\n",
    "        n = len(nums)\n",
    "        if n ==1:\n",
    "            return(nums[0])\n",
    "        \n",
    "        ## 只统计奇数，因为奇数 不会出现 可对可错 ##\n",
    "        # 所以干脆 套两层i\n",
    "        # 第一层i*2+1 才是真 i\n",
    "        L,R = 0,n//2-1\n",
    "        print(L,R)\n",
    "        while L<=R:\n",
    "            M = (L+R)//2\n",
    "            # 这才是真的M，上面的M、L、R 只是为了方便移动，确保只出奇数\n",
    "            M2 = M*2+1\n",
    "            if nums[M2-1] == nums[M2]:\n",
    "                L = M+1\n",
    "            else:\n",
    "                R = M-1\n",
    "        L2 = L*2+1\n",
    "        \n",
    "        return(nums[L2-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        a = nums[0]\n",
    "        for b in nums[1:]:\n",
    "            a = a ^ b\n",
    "\n",
    "        return(a)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
